package leetcode.editor.vscdev.hot100;

import java.util.*;

public class lc215 {
    public static void main(String[] args) {
        int k = 2;
        int[] arr = {3, 2, 1, 5, 6, 4};
        new Solution().findKthLargest(arr, k);
    }
}

class Solution {

    private final static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
        // 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
        /*
         * 最简单解法, 使用java库函数排序数组, 选取第k个元素返回
         * 当然这样就没意义了
         */
        // Arrays.sort(nums);
        // return nums[nums.length - k];
        return func1(nums, k);
    }

    private int func1(int[] nums, int k) {
        int kIndex = nums.length - k;
        // 三路快排 + 减治
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 三路快排划分过程
            int randomIndex = left + random.nextInt(right - left + 1);
            swap(nums, left, randomIndex);
            int pivot = nums[left];
            int lt = left + 1;
            int gt = right;
            int i = left + 1;
            while (i <= gt) {
                if (nums[i] < pivot) {
                    swap(nums, lt, i);
                    i++;
                    lt++;
                } else if (nums[i] > pivot) {
                    swap(nums, gt, i);
                    gt--;
                    // i 保持不变，继续处理当前位置的新元素
                } else {
                    i++;
                }
            }
            swap(nums, lt - 1, left);
            // 划分结束, 进行减治判断
            if (kIndex >= lt && kIndex <= gt) {
                return nums[kIndex];
            } else if (kIndex < lt) {
                right = lt - 1;
            } else {
                left = gt + 1;
            }
        }
        return nums[kIndex];
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
